package com.lw.leetcode.other.c;

/**
 * Created with IntelliJ IDEA.
 * 1568. 使陆地分离的最少天数
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/24 16:24
 */
public class MinDays1568 {

    private int item;
    private int next;
    private int m;
    private int n;
    private int[] arr = {0, 1, 0, -1, 1, 0, -1, 0};
    private int[][] grid;

    public int minDays(int[][] grid) {
        item = 1;
        next = 2;
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        int f = getF();
        if (f == -1) {
            return 0;
        }
        int x = f / 30;
        int y = f % 30;
        find(x, y);
        if (count()) {
            return 0;
        }
        item++;
        next++;
        for (int i = 0; i < m; i++) {
            int[] ints = grid[i];
            for (int j = 0; j < n; j++) {
                if (ints[j] == item) {
                    ints[j] = 0;
                    f = getF();
                    if (f == -1) {
                        return 1;
                    }
                    x = f / 30;
                    y = f % 30;
                    find(x, y);
                    if (count()) {
                        return 1;
                    }
                    item++;
                    next++;
                    ints[j] = item;
                }
            }
        }
        return 2;
    }

    private int getF() {
        for (int i = 0; i < m; i++) {
            int[] ints = grid[i];
            for (int j = 0; j < n; j++) {
                if (ints[j] == item) {
                    return i * 30 + j;
                }
            }
        }
        return -1;

    }

    private boolean count() {
        for (int i = 0; i < m; i++) {
            int[] ints = grid[i];
            for (int j = 0; j < n; j++) {
                if (ints[j] == item) {
                    return true;
                }
            }
        }
        return false;
    }

    private void find(int x, int y) {
        if (x < 0 || y < 0 || x == m || y == n) {
            return;
        }
        if (grid[x][y] == item) {
            grid[x][y] = next;
            for (int i = 0; i < 8; i += 2) {
                find(x + arr[i], y + arr[i + 1]);
            }
        }
    }

}
